package __贪心算法

import "strconv"

/*
https://leetcode.cn/problems/monotone-increasing-digits/description/

738.单调递增的数字
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

给定一个非负整数 N，找出小于等于N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

示例 1:
输入: N = 10
输出: 9

示例 2:
输入: N = 1234
输出: 1234

示例 3:
输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数
*/

func monotoneIncreasingDigits(n int) int {

	if n < 10 { //如果n<10,直接返回对应值即可
		return n
	}

	s := []byte(strconv.Itoa(n)) //转为byte数组
	i := 1                       //从1下标开始

	for i < len(s) && s[i] >= s[i-1] { //如果s[i] >= s[i-1],符合递增条件，就一直向后遍历
		i++
	}

	if i != len(s) { //如果i没能到达数组最后位置，进行特殊处理
		for i > 0 && s[i-1] > s[i] { //只要s[i-1] > s[i],那么s[i-1]--, i向前一位
			s[i-1]--
			i--
		}

		i++ //由于i上一步会到达第一个不符合递增条件的下标，所以i++到达第二个下标进行后续操作
		for ; i < len(s); i++ {
			s[i] = '9'
		}
	}

	ans, _ := strconv.Atoi(string(s))
	return ans
}
